﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Sorts
{
    class QuickSort<T>
        where T : IComparable<T>
    {
        private static Random _random = new Random();

        private static void Swap(T[] items, int left, int right)
        {
            if (left != right)
            {
                var temp = items[left];
                items[left] = items[right];
                items[right] = temp;
            }
        }

        public static void Sort(T[] items)
        {
            if (items.Length < 2)
            {
                return;
            }

            Sort(items, 0, items.Length - 1);
        }

        private static void Sort(T[] items, int left, int right)
        {
            if (left >= right)
            {
                return;
            }

            var pivotIndex = _random.Next(left, right);
            var newPivotIndex = Partition(items, left, right, pivotIndex);

            Sort(items, left, newPivotIndex - 1);
            Sort(items, newPivotIndex + 1, right);
        }

        private static int Partition(T[] items, int left, int right, int pivotIndex)
        {
            T pivotValue = items[pivotIndex];
            Swap(items, left, pivotIndex);
            int newPivotIndex = left;

            while (left < right)
            {
                while (left < right && items[right].CompareTo(pivotValue) >= 0)
                {
                    right--;
                }

                if (left < right)
                {
                    Swap(items, left, right);
                    left++;
                    newPivotIndex = right;
                }

                while (left < right && items[left].CompareTo(pivotValue) <= 0)
                {
                    left++;
                }

                if (left < right)
                {
                    Swap(items, left, right);
                    right--;
                    newPivotIndex = left;
                }
            }

            return newPivotIndex;
        }
    }
}
